mmmmmmmmmmm mmmmmmmm******* Mn7LCS/TM-32 AN OPERATOR EMBEDDING THEOREM FOR COMPLEXITY CLASSES OF RECURSIVE FUNCTIONS Robert Mod May 1973 MAC TECHNICAL MEMORANDUM 3 2 AN OPERATOR EMBEDDING THEOREM FOR COMPLEXITY CLASSES OF RECURSIVE FUNCTIONS Robert Moll May 1973 This research was supported in part by the National Science Foundation under research grant GJ34671, and in part by the Advanced Research Projects Agency of the Department of Defense under ARPA Order No. 433 which was monitored by ONR Contract No. N00014-70-A-0362-0001. MASSACHUSETTS INSTITUTE OF TECHNOLOGY PROJECT MAC CAMBRIDGE MASSACHUSETTS 0213 9 AN OPERATOR EMBEDDING THEOREM FOR COMPLEXITY CLASSES OF RECURSIVE FUNCTIONS f Robert Moll Massachusetts Institute of Technology Spring 1973 1. INTRODUCTION Let 3<(t) be the set of functions computable by some machine using no more than t(x) machine steps on all but finitely many arguments x. If we order the ^- classes under set inclusion as t varies over the recursive functions, then it is natural to ask how rich a structure is obtained. We show that this structure is very rich indeed. If R is any countable partial order and F is any total effective operator, then we show that there is a recursively enumerable sequence of recursive machine running times f$ ,,.} _ such that if iRk, then * s(k) J k€N ^(F($ ,. N )) Q ^($ /,n), and if j and k are incomparable, then F(§ ..,) < ~ s(j) ? s(k;r' J y ~ v s (jr $ ., . on infinitely many arguments, and F(§ ., . ) < $ ... on infinitely s(k) J ~ s(k) s(j) many arguments. An interesting feature of our proof is that we avoid appealing explicitly to the continuity of total effective operators; indeed our proof follows directly from a single appeal to the recursion theorem. Several investigators have considered this and related problems, and in Section 4 we briefly summarize these investigations and compare them to our own. -2- 2. PRELIMINARIES For notation from recursive function theory we follow Rogers [2 ]. For each n € N, P^ stands for the partial recursive functions of n-variables, and » n stands for the total recursive functions of n variables. We use (a.e.) to denote "almost everywhere", which for our purposes stands for "all but finitely many". Similarly (i.o.) stands for "infinitely often". Suppose {cDq.CPj^,...} is a Godel numbering of P . A measure on Computation [1] $ = {$ Q ,§ 1 ,...) is a sequence of functions in P satisfying 1. Vi € N [dom(co.) = dom($.)] 2. \ixy[§ (x) = y] is a recursive predicate. If we think of our Godel numbering in the usual one-tape Turing machine formalism, then $ i (x) = "the number of steps in the computation of the i th Turing machine on argument x" is a measure on computation. Henceforth let $ be some fixed measure on computation. Then we define for any total function t F(t) = [i e. N f 00. € ^, and $ s t (a.e.)}, 1 i and y(t) = {CD. I i e F(t)}. ■3- That is, F(t) is the set of (indices of ) total machines which run in time t, and 5?(t) is the set of total functions computable within time t. ^(t) is called a complexity class . A sequence of partial functions f = {\|j ,41.. , . . .] is said to be an r.e. sequence of partial functions if \ix[i|j . (x) ] € P_. 1 V The following theorem of Blum [ 1 ] shows that we can uniformly enlarge complexity classes ^(t) if t is a sufficiently well-behaved function. Theorem . (Compression Theorem) There is a g f fl such that for every §. € ft.., ^(f.)5 y(\xg(x,$ . (x)) . g is called a compression function for $ . An operator is a map which takes functions to functions; we write F(f)(x) to mean the value of the operator F applied to the function f, evaluated at x. An operator F: D £ P.. -* P is called an effective operator if there is an s € ft, such that F(© ) (x) = CD , •. (x) . — c 1 ~ e s(e; An effective operator F is total effective if for every f € ft,, F(f) is defined and F(f) f ft . 3 . THE EMBEDDING THEOREM Theorem . Let F be any total effective operator, and let R be any recursive countable partial order on N. Then there exists an r.e. sequence of recursive functions p,.., p.. , . . . p ... such that if jRk, then F(p ) < u I n ~ j p, (a.e.), and if j and k are incomparable, then F(p.) < p. (i.o.), and k ~ j K p < F(p.) (i.o.). K ~ J Proof. We assume without loss of generality that R orders N-{0} rather than N, and in addition that R contains kRO for each k > 0. Let d = < i 0' k >J a l = < l V k l > » ••• 'a n = < i n , k n >, ... be a recursive listing of all incomparable pairs in R such that if x and y are incomparable, then < x, y > and < y x > both appear infinitely often in the list. As a technical convience we define max[c5] = 0. Let s € fc 2 be the Sl function of the s-m-n theorem defined by the equation <*>-(< x ', y >) = © , ,(y) e ' s(e,x) w/ Define i|/ £ P as follows: if x < k or 3n < k such that $ (< 0, n >) > x, (1) g U s(e )j )« + ^ s(e , j ))«]) + jRk fo s(e,i)« + ^s(e,i )>WJ. (2)(i) (2) (ii) t(e, <k,x >) = where n = \m <: x[((m = 0) and (x = k )) or [(m > 0) and (k = k ) and [(Vi ( <; i <: m) ) (3z ± s: x) such that (z = k ) and (Z i+l = 2 i + § s(e,k.) (2 i)) 2=d (^^x)]]], if such an n exists and (1) is not true, and HIS* b r n (x) + F(oo .v)(x)] otherwise iRk (3) £ P since all the test computations in clauses (1) and (2) are recursive by the second measure on computation axiom. By the recursion theorem there is an e such that i|r(e, <k,x >) = cp (<k,x>); we apply the s-1-1 version of the s-m-n theorem to obtain i|f(e, <k,x>) = CD / , ,. (x) • s (,e, K) To simplify our notation we now suppress mention of e and write p, (x) = cp s(e,k) now becomes (x) . Similarly we write § (x) for $ s(e,k) (x) . Our definition »k« = r • < if x < k or 3n < k such that $ (n) < x, — P + (1) (2)(D (2)(ii) max[ p .(x) + F(p.)(x)]) jRk [P., (x) + F(p. )(x)], n n where n = um ^ x[((m = 0) and (x s k )) or [(m > 0) and (k = k ) and [(Vi(0 <; i <: m))(3z. <: x) m l such that (z_ = k.) and (z. ... = z. + § (z )) and U U 1+1 1 Pi 1 i (z = x) ] ] ] , if such an n exists and (1) is not m true, and max [n . (x) +F(n.)(x)] otherwise. i ~ i ]<X J J jRk We first establish that at most finitely many of the functions fa,} ,- can be non-total. Suppose p, (x) diverges. Since p is defined r k k€N k u by (3) at all arguments, P Q (x) must diverge, and so by (1) p (x) = for all j > x. (3) -6- We now prove that for all k p is total. Say that a n is serviced at x if Pfc ( x ) is defined by (2), and if n n is the least m =£ x satisfying the body of (2) in the definition of P k (x). We allow the possibility that P (x) may diverge. If a is n ti n _i servxced at x, (2) guarantees that x = z = £ z + $ (z ) and so n i=l i P k. i ' a n is serviced at no other argument. Moreover, if a is serviced at x n and p k (x) diverges, then for n' > n a, will never be serviced, since n n a^, is serviced at y only when y bounds the computation of $, (x) . P k Let k be an R-minimal element in the finite set (k* I p , non-total] 1 k J Then if p k (x) diverges, it must do so because of (2) (ii) . That is a ' n is serviced at x for some n, and p. must be non- total. n But suppose p. (y) diverges by an instance of (2) (ii) for some y. n This means that i^ = k for some j and a. is serviced at y. If j < n, then y must equal z but since a is serviced x, $ (z ) < x and hence J n P k. J J P (z ) must converge. If j > n , then since a is serviced at x and j J n P k (x) is assumed to diverge, a. is never serviced. Moreover i cannot J equal n, for then i would equal k . Hence p. must be non- total because n n l n of (2)(i) or (3), and so some function p., such that i'Ri is non-total. 1 n Let i be R minimal among fi' | i'R i and i' non-total} . Then n p. must be non-total by an instance of (2)(ii), say at argument y. j-l Hence i = k. for some j, and a. must be serviced at y = L z^ + 2 J 151=0 § (z ). If j < n, p. (y) must converge since a is serviced at x Pi m r K. n k J by assumption; and if j = n, then i and k are comparable, a contra- n n diction. Furthermore if i > n. then a. will never be serviced. Hence J p. is total, and we conclude that for every k p, € &,. 1 *k 1 If jRk, then F(p.)(z) ^ p, (z) for all z > m n ='max[k,i,$ (0), ~ J ^k — Pq * (1), ... $ (k-1)]. p o Po If j and k are incomparable, then < i,k > = a. , a , ... a , ... 1 q for some infinite sequence n_ < n, < n„ • • • n ••• . 12 q For arguments z > m_ p, (z) is defined by (2) or (3). Since the sequence of z.'s is strictly increasing, there is an i n such that for i > i- > z - ^ m n- At those arguments z. for i > i , i = n , p (z.) will be defined by clause (2) and p,(z.) > F(p.)(z.). A symmetric argument k 1 j 1 shows that p. > F(p_ ) (i.o. ) , and the theorem is proved. J k Corollary . Let F be any total effective operator, and let R be any countable partial order on N. Then there exists an r.e. sequence of recursive measure functions $ ... , § ,.., ... such that if jRk, then r(0) r (1) F(§ ..,) < § ,. , (a.e.) and 3?(F($ ,.Jc ?(§ ..,), and if j and k are ~ r(jX r(k) v ~ v r(j;r? r(k) y ' incomparable, then F($ ...) <$ ...(i.o.), and F($ ., . ) <§ ...(i.o.). r(j) r(k) v ~ r(k) r(j) v -8- Proof . Mostowski [ 3 ] has shown that there is a countable partial order R into which any countable partial order may be embedded. Moreover, Sacks [4] has shown that r" is recursive. We assume without loss of generality that F is at least as large as the identity operator, and that the compression function for $, g, is strictly increasing in its second argument. Blum [ 1 ] has shown that there is an h € ^ 2 such that for all i cp.(x) < h(x, § . (x)) (a. e. ) . We assume that h is strictly increasing in its second argument. To prove the corollary, apply the theorem to r'', rewrite clause (2) as max [p (x>h(x,g(x,F($ )(x)))] + [ p . ( x ) + h(x,g(x,F($ )(x)))], J*X J ~ Pj L n ~ Pi iRk n and we rewrite clause (3) as max[p.(x) + h(x,g(x,F($ )(x)))] jRk j*x J ~ Pj It is easy to see that the theorem goes through as before, and the monotonicity restrictions on g and h guarantee that the functions {$ } k g N satisfy the corollary, k 4 . RELATION TO OTHER WORK, AND OPEN PROBLEMS McCreight [5] is the first investigator to prove an embedding theorem for subrecursive classes. He shows that any countable partial order can be embedded in the complexity classes ordered under set inclusion. However, his theorem is weaker than our results in that the functions of his partial order are "separated" by composition with a fixed recursive function, whereas our functions are separated by a total effective operator. In [6] Enderton also proves a universal embedding theorem for subrecursive classes. His notion of a sub- recursive class is quite weak, however, and his result is an immediate corollary of McCreight 's theorem. Early work on the structure of subrecursive classes was done by Feferman [12], Meyer and Ritchie [7], and Basu [8]. Feferman shows that dense chains exist for various notions of subrecursive classes. Meyer and Ritchie define what they call elementary honest classes, and they show the existence of dense chains and infinite anti-chains for such classes. Moreover, they are able to exhibit certain functions f such that dense chains of classes will exist between f and the iterate of f, \x[f (x)]. Basu builds dense chains of subrecursive classes, where these classes are closed under the application of a fixed recursive operator. Machtey [11] has announced universal embedding theorems for both the "honest" primitive recursive degrees and the "dishonest" primitive recursive degrees. Both of these theorems follow immediately from our results. W^ •'5**»!tW«I ji.j.m uv r 4«WilHWWWWai -10- We also note that Alton [ 9 ^hM^^penfeptiL*.; announced our embedding theorem. We leave open the question of the size of the functions In our embedding theorem. That is, given F, what is a reasonable upper bound on the sise of p Q in terms of F(recall that "^ bounds all the functions (P k ) keN on all arguments). * The author wishes to acknowledge the generous assistance of Professor Albert R. Meyer in the conception and preparation of this paper. -11- REFERENCES 1. M. Blum, A machine- independent theory of the complexity of recursive functions, JACM 14 , 1967, 322-336. 2. H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, 1967. it 3. A. Mostowski, Uber gewisse universelle relationen, Ann . Soc . Polon . Math. 17, 1938, 117-118. A. G. Sacks, Degrees of unsolvability, Annuals of Math . Studies , No. 55, Princeton, N.J. 1963. 5. E. McCreight, Classes of computable functions defined by bounds on computation, Doctoral Dissertation, Carnegie-Mellon University, Department of Computer Science, 1969. 6. H. Enderton, Degrees of computational complexity, JCSS No . 6, 1972, 389-396. 7. A. Meyer and D. Ritchie, Classification of functions by compu- tational complexity, Proc . of the Hawaii Internat' 1 Conf . on Sys . Sciences , 1968, 17-19. 8. S.K. Basu, On classes of computable functions, ACM Symp . on Theory of Computing , 1969, 55-61. 9. D. Alton, Operator embeddability in computational complexity, Notices of the AMS, 1972, A-763. 10. A. Meyer and P. Fischer, Computational speed-up by effective operators, JSL, No. 37, 1972, 55-68. 11. M. Machtey, Augmented loop languages and classes of computable functions, JCSS , to appear. 12. S. Feferman, Classifications of recursive functions by means of hierarchies, Trans , of the AMS, No. JL04, 1962, 101-122. UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA -R&D (Security classification of title, body of abstract and indexing annotation must be entered when the overall report is classified) i. originating ACTIVITY (Corporate author) MASSACHUSETTS INSTITUTE OF TECHNOLOGY PROJECT MAC 2a. REPORT SECURITY CLASSIFICATION UNCLASSIFIED 2b. GROUP NONE 3 REPORT TITLE AN OPERATOR EMBEDDING THEOREM FOR COMPLEXITY CLASSES OF RECURSIVE FUNCTIONS 4. descriptive NOTES (Type of report and inclusive dates) INTERIM SCIENTIFIC REPORT 5 authORIS) (First name, middle initial, last name) ROBERT MOLL 6. REPORT DATE M&Y 17, 1973 7a. TOTAL NO. OF PAGES 11 lb. NO. OF REFS 12 3a. CONTRACT OR GRANT NO. 9a, ORIGINATOR'S REPORT NUMBER(S) N00014-70-A-036 2-0006 fa. PROJ EC T NO. MAC TM-32 9b. OTHER REPORT NO(S) (Any other numbers that may be assigned this report) NONE 10. DISTRIBUTION STATEMENT DISTRIBUTION OF THIS DOCUMENT IS UNLIMITED 11 SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY OFFICE OF NAVAL RESEARCH 13. ABSTRAC T Let ^(t) be the set of functions computable by some machine within time bound t(x) for all but finitely many arguments. If F is any total effective operator and R is any recursive countable partial order, then there is an r.e. sequence of recursive machine running times T , T^ . . . , T , ... such that if iRj then 3 J (F(T i >) C". S?(T.), and if i and j are incomparable, then F( T i ) < T .= (i»°«)» J *J and F(T.) < T. (i.o.). DD, f n o r v m 65 1473 < PAGE " UNCLASSIFIED S/N 0102-014- 6600 Security Classification UNCLASSIFIED Security Classification KEY WO RDS recursive partial order complexity class total effective operator DD , F N °o R vM473 back) (PAGE 2) UNCLASSIFIED Security Classification